#! /usr/bin/env python

from optparse import OptionParser
import random


def hfunc(index):
    if index == -1:
        return 'MISS'
    else:
        return 'HIT '


def vfunc(victim):
    if victim == -1:
        return '-'
    else:
        return str(victim)


class PagePolicyCore:
    def __init__(self, addresses='-1', addressfile='', numaddrs=10, policy='FIFO', clockbits=2,
                 cachesize=3, maxpage=10, seed=0, notrace=False, compute=False):
        parser = OptionParser()
        parser.add_option('-a', '--addresses', default=addresses,
                          help='a set of comma-separated pages to access; -1 means randomly generate', action='store',
                          type='string', dest='addresses')
        parser.add_option('-f', '--addressfile', default=addressfile, help='a file with a bunch of addresses in it',
                          action='store',
                          type='string', dest='addressfile')
        parser.add_option('-n', '--numaddrs', default=numaddrs,
                          help='if -a (--addresses) is -1, this is the number of addrs to generate', action='store',
                          type='string', dest='numaddrs')
        parser.add_option('-p', '--policy', default=policy,
                          help='replacement policy: FIFO, LRU, OPT, UNOPT, RAND, CLOCK',
                          action='store', type='string', dest='policy')
        parser.add_option('-b', '--clockbits', default=clockbits, help='for CLOCK policy, how many clock bits to use',
                          action='store',
                          type='int', dest='clockbits')
        parser.add_option('-C', '--cachesize', default=cachesize, help='size of the page cache, in pages', action='store',
                          type='string', dest='cachesize')
        parser.add_option('-m', '--maxpage', default=maxpage,
                          help='if randomly generating page accesses, this is the max page number', action='store',
                          type='string', dest='maxpage')
        parser.add_option('-s', '--seed', default=seed, help='random number seed', action='store', type='string',
                          dest='seed')
        parser.add_option('-N', '--notrace', default=notrace, help='do not print out a detailed trace',
                          action='store_true',
                          dest='notrace')
        parser.add_option('-c', '--compute', default=compute, help='compute answers for me', action='store_true',
                          dest='solve')

        (self.options, self.args) = parser.parse_args()
        self.deal_args()

    def deal_args(self):
        options = self.options
        addresses = options.addresses
        addressFile = options.addressfile
        numaddrs = options.numaddrs
        cachesize = options.cachesize
        seed = options.seed
        maxpage = options.maxpage
        policy = options.policy
        notrace = options.notrace
        clockbits = options.clockbits

        random.seed(seed)

        addrList = []
        if addressFile != '':
            fd = open(addressFile)
            for line in fd:
                addrList.append(int(line))
            fd.close()
        else:
            if addresses == '-1':
                # need to generate addresses
                for i in range(0, numaddrs):
                    n = int(maxpage * random.random())
                    addrList.append(n)
            else:
                addrList = addresses.split(',')

        if not options.solve:
            print('Assuming a replacement policy of %s, and a cache of size %d pages,' % (policy, cachesize))
            print('figure out whether each of the following page references hit or miss')
            print('in the page cache.\n')

            for n in addrList:
                print('Access: %d  Hit/Miss?  State of Memory?' % int(n))
            print('')

        else:
            if notrace is False:
                print('Solving...\n')

            # init memory structure
            count = 0
            memory = []
            hits = 0
            miss = 0

            if policy == 'FIFO':
                leftStr = 'FirstIn'
                riteStr = 'Lastin '
            elif policy == 'LRU':
                leftStr = 'LRU'
                riteStr = 'MRU'
            elif policy == 'MRU':
                leftStr = 'LRU'
                riteStr = 'MRU'
            elif policy == 'OPT' or policy == 'RAND' or policy == 'UNOPT' or policy == 'CLOCK':
                leftStr = 'Left '
                riteStr = 'Right'
            else:
                print('Policy %s is not yet implemented' % policy)
                exit(1)

            # track reference bits for clock
            ref = {}

            cdebug = False

            # need to generate addresses
            addrIndex = 0
            for nStr in addrList:
                # first, lookup
                n = int(nStr)
                try:
                    idx = memory.index(n)
                    hits = hits + 1
                    if policy == 'LRU' or policy == 'MRU':
                        update = memory.remove(n)
                        memory.append(n)  # puts it on MRU side
                except:
                    idx = -1
                    miss = miss + 1

                victim = -1
                if idx == -1:
                    # miss, replace?
                    # print 'BUG count, cachesize:', count, cachesize
                    if count == cachesize:
                        # must replace
                        if policy == 'FIFO' or policy == 'LRU':
                            victim = memory.pop(0)
                        elif policy == 'MRU':
                            victim = memory.pop(count - 1)
                        elif policy == 'RAND':
                            victim = memory.pop(int(random.random() * count))
                        elif policy == 'CLOCK':
                            if cdebug:
                                print('REFERENCE TO PAGE', n)
                                print('MEMORY ', memory)
                                print('REF (b)', ref)

                            # hack: for now, do random
                            # victim = memory.pop(int(random.random() * count))
                            victim = -1
                            while victim == -1:
                                page = memory[int(random.random() * count)]
                                if cdebug:
                                    print('  scan page:', page, ref[page])
                                if ref[page] >= 1:
                                    ref[page] -= 1
                                else:
                                    # this is our victim
                                    victim = page
                                    memory.remove(page)
                                    break

                            # remove old page's ref count
                            if page in memory:
                                assert ('BROKEN')
                            del ref[victim]
                            if cdebug:
                                print('VICTIM', page)
                                print('LEN', len(memory))
                                print('MEM', memory)
                                print('REF (a)', ref)

                        elif policy == 'OPT':
                            maxReplace = -1
                            replaceIdx = -1
                            replacePage = -1
                            # print 'OPT: access %d, memory %s' % (n, memory)
                            # print 'OPT: replace from FUTURE (%s)' % addrList[addrIndex+1:]
                            for pageIndex in range(0, count):
                                page = memory[pageIndex]
                                # now, have page 'page' at index 'pageIndex' in memory
                                whenReferenced = len(addrList)
                                # whenReferenced tells us when, in the future, this was referenced
                                for futureIdx in range(addrIndex + 1, len(addrList)):
                                    futurePage = int(addrList[futureIdx])
                                    if page == futurePage:
                                        whenReferenced = futureIdx
                                        break
                                # print 'OPT: page %d is referenced at %d' % (page, whenReferenced)
                                if whenReferenced >= maxReplace:
                                    # print 'OPT: ??? updating maxReplace (%d %d %d)' % (replaceIdx, replacePage, maxReplace)
                                    replaceIdx = pageIndex
                                    replacePage = page
                                    maxReplace = whenReferenced
                                    # print 'OPT: --> updating maxReplace (%d %d %d)' % (replaceIdx, replacePage, maxReplace)
                            victim = memory.pop(replaceIdx)
                            # print 'OPT: replacing page %d (idx:%d) because I saw it in future at %d' % (victim, replaceIdx, whenReferenced)
                        elif policy == 'UNOPT':
                            minReplace = len(addrList) + 1
                            replaceIdx = -1
                            replacePage = -1
                            for pageIndex in range(0, count):
                                page = memory[pageIndex]
                                # now, have page 'page' at index 'pageIndex' in memory
                                whenReferenced = len(addrList)
                                # whenReferenced tells us when, in the future, this was referenced
                                for futureIdx in range(addrIndex + 1, len(addrList)):
                                    futurePage = int(addrList[futureIdx])
                                    if page == futurePage:
                                        whenReferenced = futureIdx
                                        break
                                if whenReferenced < minReplace:
                                    replaceIdx = pageIndex
                                    replacePage = page
                                    minReplace = whenReferenced
                            victim = memory.pop(replaceIdx)
                    else:
                        # miss, but no replacement needed (cache not full)
                        victim = -1
                        count += 1

                    # now add to memory
                    memory.append(n)
                    if cdebug:
                        print('LEN (a)', len(memory))
                    if victim != -1:
                        assert (victim not in memory)

                # after miss processing, update reference bit
                if n not in ref:
                    ref[n] = 1
                else:
                    ref[n] += 1
                    if ref[n] > clockbits:
                        ref[n] = clockbits

                if cdebug:
                    print('REF (a)', ref)

                if notrace is False:
                    print('Access: %d  %s %s -> %12s <- %s Replaced:%s [Hits:%d Misses:%d]' % (
                        n, hfunc(idx), leftStr, memory, riteStr, vfunc(victim), hits, miss))
                addrIndex += 1

            print('')
            print('FINALSTATS hits %d   misses %d   hitrate %.2f' % (
                hits, miss, (100.0 * float(hits)) / (float(hits) + float(miss))))
            print('')


def main():
    core = PagePolicyCore()


if __name__ == "__main__":
    main()
